package com.leetcode_mianshi_150.tree;

import com.sun.xml.internal.messaging.saaj.packaging.mime.util.QEncoderStream;
import org.junit.Test;

import java.util.*;

/**
 * @author: 临晖
 * @since: 2024-05-11
 */
public class Solution {

    /**
     * 212. 单词搜索 II
     * 尝试过
     * 困难
     * 相关标签
     * 相关企业
     * 提示
     * 给定一个 m x n 二维字符网格 board 和一个单词（字符串）列表 words， 返回所有二维网格上的单词 。
     * 单词必须按照字母顺序，通过 相邻的单元格 内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。
     *
     * @param board
     * @param words
     * @return
     */
    int[][] dirs = {{0, -1}, {-1, 0}, {1, 0}, {0, 1}};
    public List<String> findWords(char[][] board, String[] words) {
        Trie trie = new Trie();
        //构建字典树
        for (String word : words) {
            trie.insert(word);
        }

        Set<String> res = new HashSet<>();

        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                dfs(board, trie, i, j, res);
            }
        }

        return new ArrayList<>(res);
    }

    /**
     *
     * 深搜
     *
     * @param board
     * @param trie
     * @param i
     * @param j
     * @param res
     */
    private void dfs(char[][] board, Trie trie, int i, int j, Set<String> res) {
        char c1 = board[i][j];
        if (c1 == '#' || trie.children[c1 - 'a'] == null) {
            return;
        }

        String word = trie.children[c1 - 'a'].world;
        if (word != null && !"".equals(word)) {
            res.add(word);
        }

        board[i][j] = '#';

        for (int[] dir : dirs) {
           int dirI = i + dir[0];
           int dirJ = j + dir[1];

            if (dirI >= 0 && dirI < board.length && dirJ >= 0 && dirJ < board[0].length) {
                dfs(board, trie.children[c1 - 'a'], dirI, dirJ, res);
            }
        }

        board[i][j] = c1;
    }

    @Test
    public  void main() {
        char[][] board = {{'o','a','a','n'},{'e','t','a','e'},{'i','h','k','r'},{'i','f','l','v'}};
        String[] words = {"oath","pea","eat","rain"};

        findWords(board, words).stream().forEach(System.out::println);
    }

}
